class Solution
{
public:
    long long putMarbles(vector<int> &weights, int k)
    {
        int n = weights.size();
        if (n == 1)
        {
            return 0;
        }
        vector<long long> values(n - 1);
        for (int i = 0; i < n - 1; ++i)
        {
            values[i] = weights[i] + weights[i + 1];
        }

        sort(values.begin(), values.end());
        long long result = 0;

        // 不能直接求和，会溢出
        // result += accumulate(values.end() - k + 1, values.end(), 0);
        // result -= accumulate(values.begin(), values.begin() + k - 1, 0);

        // 避免中间结果溢出
        for (int i = 0; i < k - 1; ++i)
        {
            result -= values[i];
            result += values[n - 2 - i];
        }

        return result;
    }
};